package com.chao.sort;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description : 堆排序
 * @date : 2023/7/10
 */
public class HeapSort {

    public static void main(String[] args) {
        int []arr = new int[] {5,0,3,8,3,4,52,32,26,19,36};
        sort(arr);
        System.out.println(Arrays.toString(arr));;
    }

    private static void sort(int[] arr) {
        // 构建大顶堆
        heapIfy(arr,arr.length);
        for (int i = arr.length - 1; i >= 0; i--) {
            // 交换第一个元素和最后一个元素的值
            swap(arr,0,i);
            // 忽略最后元素继续堆化
            heapIfy(arr,i);
        }
    }

    private static void heapIfy(int[] arr,int size) {
        for (int i = size / 2 - 1; i >= 0; i--) {
            buildMaxRootHeap(arr,i, size);
        }
    }

    private static void buildMaxRootHeap(int[] arr,int i,int size) {
        int maxIndex = i;
        int left = getLeftSonIndex(i);
        int right = getRightSonIndex(i);

        if (left < size && arr[left] > arr[maxIndex]) {
            maxIndex = left;
        }

        if (right < size && arr[right] > arr[maxIndex]) {
            maxIndex = right;
        }

        if (maxIndex != i) {
            swap(arr,maxIndex,i);
            buildMaxRootHeap(arr,maxIndex,size);
        }
    }

    private static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static int getLeftSonIndex(int i) {
        return 2*i+1;
    }

    private static int getRightSonIndex(int i) {
        return 2*i+2;
    }
}
